3-Symmetric Permutations
I want to study patterns inside permutations. Consider a permutation of size 4: 1432. Today I am excited by ordered subset of size 3 inside this permutation. For example, I can drop the last number and look at 143. The ordering in 143 is the same as in 132, or, as a mathematician would say, 143 is order-isomorphic to 132. In my example of 1432, I have four subsets depending on which number I remove: 432 is order-isomorphic to 321, while 132, 142 and 143 are all order-isomorphic to 132.
The density of a pattern 123 in the permutation 1432 is the ratio of subsets of size 3 that are order-isomorphic to 123 to all subsets of size 3. As I already calculated, the density of 123 in 1432 is zero, while the density of 321 is 1/4, and the density of 132 is 3/4.
A permutation is called 3-symmetric if the densities of all patterns of size 3 (123, 132, 213, 231, 312, 321) are the same. The reason I love this notion, is that 3-symmetric permutations are similar to random permutations with respect to patterns of size 3.
My example permutation, 1432, is not 3-symmetric. Thinking about it, no permutation of size 4 can be 3-symmetric. The number of subsets of size 3 is four, which is not divisible by 6.
I wanted to find 3-symmetric permutations. So the size n of the permutation needs to be such that n choose 3 is divisible by 6. The numbers with this property are easy to find. The sequence starts as 1, 2, 9, 10, 18, 20, 28, 29, 36, 37, 38, 45, 46. The sequence is periodic with period 36.
Any permutation of sizes 1 or 2 is 3-symmetric as all densities are zero. Duh!
The next interesting size is 9. My student, Eric Zhang, wrote a program and found that there are two 3-symmetric permutations of size 9: 349852167 and 761258943. These numbers are so cool!. First, they are reverses of each other. This is not very surprising: if a permutations is 3-symmetric, then its reverse must also be 3-symmetric. There is another property: the permutations are rotational symmetries of each other. That is, the sum of two digits in the same place is 10. You can see that rotating a 3-symmetric permutation produces a 3-symmetric permutation.
I decided to write a program to find 3-symmetric permutations of the next size: 10. There is none. I do not trust my programming skills completely, so adjusted my program to size 9 and got the same result as Eric. I trust Eric’s programming skills, so I am pretty sure that there are no 3-symmetric permutations of size 10. Maybe there are some 3-symmetric permutations in size 18.
Let’s find 2-symmetric permutations. These are permutations with the same number of ascends and descends inversions and non-inversions. For n to be the size of such permutation n choose 2 needs to be divisible by 2. That means n has to have remainder 0 or 1 modulo 4. The first nontrivial case is n = 4. There are six 2-symmetric permutations: 1432, 2341, 2413, 3142, 3214, 4123. We can also group them into reversible pairs: 1432 and 2341, 2413 and 3142, 3214 and 4123. If we look at rotational symmetry we get different pairs: 1432 and 4123, 2341 and 3214, 2413 and 3142.
You can try to find non-trivial 4-symmetric permutations. Good luck! The smallest nontrivial size is 33. Finding 5-symmetric permutations is way easier: the smallest nontrivial size is 28. The sequence of nontrivial sizes as a function of n is: 1, 4, 9, 33, 28, 165, 54, 1029, 40832, 31752, 28680, 2588680, 2162700, and so on. My computer crashed while calculating it.
Share:
Leo Broukhis:
s/no any/none/
23 October 2018, 3:43 pmDrake Thomas:
The number of 2-balanced permutations of 4, 5, 8, 9 are 6, 22, 3836, 29228 respectively. The ones for 5 are 14532, 15342, 15423, 23541, 24351, 24513, 25143, 25314, 31542, 32451, 32514, 34152, 34215, 35124, 41352, 41523, 42153, 42315, 43125, 51243, 51324, 52134.
I would expect these numbers to be a result of some simple computation, but they’re weird: 3836 has a factor of 137. Not sure what’s going on here, and it suggests a basic combinatorial argument probably won’t cut it (I was thinking something about viewing the permutation as a chosen breakpoint in a circular rearrangement of 1,…,n, since from that perspective everything is nice with respect to 2-balancing or its analogue, but this doesn’t seem to lead anywhere nice).
There’s also something going on with the allowable cycle decompositions in these things ((a,b,c) means cycles of lengths a, b, c with multiplicity):
* 4 only has (4) and (1,1,2)
* 5 has (1,4) (2,3) (1,1,1,2)
* 8 has (1,1,1,1,2,2) (1,1,1,5) (1,1,2,4) (1,1,3,3) (1,2,2,3) (2,2,2,2) (1,7) (2,6) (3,5) (4,4)
I haven’t thought about this to tell whether the ones that don’t occur are trivially rules out by some simple consideration.
Curiously enough, this sequence (both with added zeros and without) isn’t in the OEIS, nor is your list of nontrivial sizes; I would have expected something this simple to show up at least in the case of 2.
I can also confirm your results for 3-balanced permutations of sizes 9 and 10.
24 October 2018, 3:33 amtanyakh:
Drake,
The sequence of the number of 2-balanced permutations is submitted, but is not approved yet. I was planning to submit more sequences on the subject.
24 October 2018, 9:35 amtanyakh:
Thank you Leo,
I fixed the typo.
24 October 2018, 11:52 amDrake Thomas:
Some other notes:
The reason that the number of permutations of 5 is not a multiple of 4 is because the pair 25314 41352 is closed under reversal AND element-wise inversion, so it only generates 2 permutations from the seed instead of 4. (This happens for 9 too, but the number of such pairs is 150, an even number.)
Iterating through all permutations for large values is computationally intractable, so I checked some things probabilistically: none of 54,000,000 random permutations of 18 elements were 3-balanced, though with only one nontrivial datapoint it’s hard to tell what our expected density should be – there could easily be millions and I wouldn’t expect to have encountered any.
At least one 2-balanced permutation exists for every multiple of 4: if n=4k, we take (1,2,…k,4k-k+1,4k-k+2,…,4k,4k-k,4k-k-1,….k+2,k+1). I’m less sure about things which are 1 mod 4; the similar pattern I tried breaks down in the 20s.
The 3-balanced patterns for 9 have this nice structure if you plot them; you’ve got this symmetric structure about 5, with alternatingly increasing and decreasing runs of equal length. Sadly, this fails to be 3-balanced for 29, the next 3-valid number congruent to 1 mod 4.
25 October 2018, 2:49 pmTanya Khovanova's Math Blog » Blog Archive » 3-Symmetric Graphs:
[…] « 3-Symmetric Permutations […]
30 October 2018, 6:55 pmTanya Khovanova's Math Blog » Blog Archive » Symmetries of k-Symmetric Permutations:
[…] all possible patterns of of size three with the same frequency. As I mentioned in my recent post 3-Symmetric Permutations, the smallest non-trivial examples are in size […]
25 November 2018, 4:44 pmTanya Khovanova's Math Blog » Blog Archive » 3-Inflatable Permutations:
[…] contain all possible patterns of size k with the same frequency. As I mentioned in my recent post 3-Symmetric Permutations, the smallest non-trivial examples of 3-symmetric permutations are 349852167 and 761258943 in size […]
27 November 2018, 2:13 pmAngelo Scordo:
reference to the Drake Thomas comment on 2-simmetric permutations of size 5 and 8. I did computation for these sizes and found the same results 22 and 3836 balanced permutations. I extended the calculations to all the set of n=5 permutations with the following results:
var STD perm#
0 0 22
1 1 40
4 2 30
9 3 18
16 4 8
25 5 2
There are 22 permutations with variance 0 perfectly balanced, 40 with variance 1, and so on….
If we form this sequence: 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1 and make a search into OEIS
we found that this sequence formed by the number of permutations of each unbalanced class divided by 2 and in decreasing order
with respect to the variance followed by the number of balanced permutations followed again by the number of permutations of
each unbalanced class divided by 2 in ascending order is the sequence A008302 Triangle of Mahonian numbers T(n,k).
I did the same for n=8 with the following results:
var STD perm#
0 0 3836
1 1 7472
4 2 6900
9 3 6034
16 4 4986
25 5 3880
36 6 2830
49 7 1922
64 8 1204
81 9 686
100 10 348
121 11 152
144 12 54
169 13 14
196 14 2
We can form in the same manner the following sequence:
1, 7, 27, 76, 174, 343, 602, 961, 1415, 1940, 2493, 3017, 3450, 3736, 3836, 3736, 3450, ……. uo to 1
and we found that also this sequence is part of the sequence A008302 Triangle of Mahonian numbers T(n,k)
for different n and k.
Please Tanya give my e-mail address to Drake Thomas and let me know your comment. For your knowledge I did not have an education in
3 December 2018, 8:50 ammath and do it for fun, so I’m not able to proceed further without your help. But I will cooperate if you think this worth of attention,
have a lot of additional material and ideas.
Angelo Scordo:
Interesting consideration:
5 December 2018, 3:34 amThe sequence A008302 – OEIS – Triangle of Mahonian numbers T(n,k): coefficients in expansion of Product_{i=0..n-1} (1 + x + … + x^i), where k ranges from 0 to A000217(n-1), presents a connection to the density distribution of 2-symmetrical permutation.
If we take the following subsequences:
n=4 [T(8)..T(14)]
n=5 [T(15)..T(25)]
n=8 [T(64)..T(92)]
n=9 [T(93)..T(129)]
we can notice that these are exactly the number of permutations of order n which are order-isomorphic to (12) or (21) starting from the first, which is
the class (only one element) with only (12) type permutations, proceeding with increasing (21) and decreasing (12) densities, up to the 2-symmetric position wich is in trhe center of sequence. From this point the sequence proceeds always increasing (21) and decreasing (12) up to the final class (only 1 element) wich indicates the only permutation with all (21) type.
Angelo Scordo:
with reference to my comment of 3 December there is a typo problem
the 2 tables are wrongly formatted because of tabs wich where not transferred correctly, change as follows with blanks.
var STD perm#
0 0 6
1 1 10
4 2 6
9 3 2
var STD perm#
0 0 3836
1 1 7472
4 2 6900
9 3 6034
16 4 4986
25 5 3880
36 6 2830
49 7 1922
64 8 1204
81 9 686
100 10 348
121 11 152
144 12 54
169 13 14
196 14 2
Than you
Angelo
6 December 2018, 3:15 pmAngelo Scordo:
A direct formula for 2-symmetric permutation of order n.
From my post of 5 december it is possible to derive a faormula for the direct calculation of the number of 2-symmetric permutation.
The formula is
if(n%4<2,print(T(n,n*(n-1)/4)))
A formula for T(n,k) can be found in OEIS A008302.
This is the result for n from 2 to 23
2 is not
3 is not
4 is 2-symmetric with 6 elements
5 is 2-symmetric with 22 elements
6 is not
7 is not
8 is 2-symmetric with 3836 elements
9 is 2-symmetric with 29228 elements
10 is not
11 is not
12 is 2-symmetric with 25598186 elements
13 is 2-symmetric with 296643390 elements
14 is not
15 is not
16 is 2-symmetric with 738680521142 elements
17 is 2-symmetric with 11501573822788 elements
18 is not
19 is not
20 is 2-symmetric with 62119523114983224 elements
21 is 2-symmetric with 1214967840930909302 elements
22 is not
23 is not
The formula works up to 100 and more Than the calculation time start to increase exponentially.
for n = 100 I got:
n=100;if(n%4<2,print(T(n,n*(n-1)/4)))
11 December 2018, 8:19 am221162231799801437337491422676415187183834729960140576944399302421324901266274924973791449425648337816306724828465719503145180465615716643026616888287189208
this number has 156 digits.
Angelo Scordo:
I want to explain better what the triangle of Mac Mahon does:
As an example take n=4 which is 2-symmetric.
The 24 permutations of this group are diveded into classes according to the content of permutation isomorphic to (12) or (21)
let us call the group using the number of permutations of each type, they are:
n=4 classes :(6,0) (5,1) (4,2) (3,3) (2,4) (1,5) (0,6)
n=4 elements: 1, 3, 5, 6, 5, 3, 1 the 4th line of Mac Mahon triangle tell us how many elements are in each class
I also modified the OEIS A008302 formula to produce one line of the Mac Mahon triangle
The modified formula is as follows:
{TL(n) = local(v=vector(n*(n-1)/2+1));my(A=1+x); for(i=1,n, A = 1 + intformal(A – q*subst(A,x,q*x +x^2*O(x^n)))/(1-q));
v=vector(#v,k,polcoeff(n!*polcoeff(A,n,x),k-1,q));}
The first 8 lines of the triangle.
line 1: [1]
line 2: [1, 1]
line 3: [1, 2, 2, 1]
line 4: [1, 3, 5, 6, 5, 3, 1]
line 5: [1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1]
line 6: [1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1]
line 7: [1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, 573, 531, 455, 359, 259, 169, 98, 49, 20, 6, 1]
line 8: [1, 7, 27, 76, 174, 343, 602, 961, 1415, 1940, 2493, 3017, 3450, 3736, 3836, 3736, 3450, 3017, 2493, 1940, 1415, 961, 602, 343, 174, 76, 27, 7, 1]
It is improper to use the name triangle because the lenth of line don’t increase in linear manner being equal to C(n,2)+1 the combinations.
12 December 2018, 4:18 pmAngelo Scordo:
Who was Percy Mac Mahon. Mac Mahon (1854-1929) was born in Malta to a British military family. He served as an official in the english army in India. In early 1878 MacMahon returned to England and the sequence of events began which led to him becoming a mathematician rather than a soldier.
14 December 2018, 3:32 pmMacMahon was elected a fellow of the Royal Society in 1890. He received the Royal Society Royal Medal in 1900, the Sylvester Medal in 1919, and the Morgan Medal by the London Mathematical Society in 1923. MacMahon was the President of the London Mathematical Society from 1894 to 1896.
MacMahon is best known for his study of symmetric functions and enumeration of plane partitions; see MacMahon Master theorem. His two volume Combinatory analysis, published in 1915/16,[2] is the first major book in enumerative combinatorics.
In the movie The Man Who Knew Infinity Kevin McNally plays as MacMahon. The film accurately depicts the first meeting of MacMahon and Srinivasa Ramanujan, where Ramanujan successfully completes some mathematical calculations.
You can see Kevin McNally where https://en.wikipedia.org/wiki/Kevin_McNally.
Has someone of you seen the movie?
Angelo Scordo:
I forgot to mention that Mac Mahon did develop many puzzles, among them the Mac Mahon coloured cubes see
16 December 2018, 1:47 pmalso: https://www.mathematische-basteleien.de/macmahon.htm.
Angelo Scordo:
Some furter considarations:
17 December 2018, 8:42 am– The lines of Mac Mahon triangle can be thought as a frequency distribution of permutations.
– For Mac Mahon about one century ago, these numbers indicated the permutations with identical number of inversions,
we talk of subsets of size 2 order isomorphic to 12 and 21, the two definitions are equivalent. (need demonstration).
– From a statistics point of view we can see the Mac Mahon triangle with n growing as a new distribution I call it
“Mac Mahon distribution” in analogy to binomial and standard distribution.
– I conjecture that this distribution for n going to infinity approach the standard distribution.
– I have started investigation to extend these concept to 3-symmetric and k-symmetric subsets.
– I NEED YOUR HELP TO FOUND THE SUBSETS STRUCTURE AND BEHAVIOUR. SOMEONE WANT TO COOPERATE ?
Angelo Scordo:
A Civil Engineering lesson, ( being an engineer I can’t avoid to make consideration related to my field of activity ),
20 December 2018, 4:18 amcould call the Identity permutation and its reverse as the configurations with maximum stiffness.
From the bell shaped distribution we know that the frequencies distribution on the extreme tail of the curve
are very low if compared to the center near to the vertex.
This is a good lesson because says that obtaining high stiffness does not arrive accidentally but
need geat efforts in search for proper design and calculations.
There are very important case of errors in stiffness calculation, one of them ia the Citicorp skyscraper the forth in
height in New York City which suffered from such a problem.
Angelo Scordo:
Again on connections between Civil Engineering and permutations.
2 January 2019, 4:14 amThe correct response of the structure of a skyscraper to external stresses such as wind, depends on the rigidity of the pillars and their distribution on the basis of the skyscraper.
Well, from the analogies demonstrated with the 2-symmetric distribution we know that the maximum stiffness is at the tails of the permutations distribution, while the 2-symmetric distribution is in the center of the distribution and is above all if we are looking for the 2-supersymmetric case I talked in the 16 dec post.
The correct response to wind stress requires that the load-bearing pillars possess both characteristics, each of which has a very low probability of being obtained without design efforts.